
/*
畅通路径:途经单元格的个数
找最短的：BFS (更高效)
DFS:找一个可行解更高效
*/

class Solution {
public:
int size ;
int step = 0;
int dx[8] = {1,1,0,-1,1,-1,0,-1};
int dy[8] = {1,0,1,1,-1,0,-1,-1};

    class Node{
        public:
        int x;
        int y;
        int step;
        Node(int nx,int ny,int ns){
            x=nx;y=ny;step=ns;
        }
    };

    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        size = grid.size();
        if (grid[0][0]==1||grid[size-1][size-1]==1) return -1;
        if (size==1||size==2) return size;
        Node begin(0,0,1);queue<Node> q;q.push(begin);
        while(!q.empty()){
            Node temp = q.front();q.pop();
            for(int i=0;i<8;i++){
                int nx = temp.x + dx[i];
                int ny = temp.y + dy[i];
                if (nx>=0&&nx<size&&ny>=0&&ny<size&&grid[nx][ny]==0){
                    if (nx==size-1&&ny==size-1){
                    return temp.step+1;
                }
                Node next(nx,ny,temp.step+1);
                    q.push(next);
                    grid[nx][ny] = 1;
                }
            }
        }

        return -1;
    }
};